равнение направо! - traduction vers français

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа ${\displaystyle x}$ в натуральную степень ${\displaystyle n}$ за меньшее число умножений, чем это требуется в определении степени. Многие из этих алгоритмов основаны на том, что для возведения числа ${\displaystyle x}$ в степень ${\displaystyle n}$ не обязательно перемножать число ${\displaystyle x}$ на само себя ${\displaystyle n}$ раз, а можно перемножать уже вычисленные степени. В частности, если ${\displaystyle n=2^{k}}$ степень двойки, то для возведения в степень ${\displaystyle n}$ достаточно число возвести в квадрат ${\displaystyle k}$ раз, затратив при этом ${\displaystyle k}$ умножений вместо ${\displaystyle 2^{k}}$. Например, чтобы возвести число ${\displaystyle x}$ в восьмую степень, вместо выполнения семи умножений ${\displaystyle x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x}$ можно возвести число в квадрат (${\displaystyle x^{2}=x\cdot x}$), потом результат возвести ещё раз в квадрат и получить четвёртую степень (${\displaystyle x^{4}=x^{2}\cdot x^{2}}$), и наконец результат ещё раз возвести в квадрат и получить ответ (${\displaystyle x^{8}=x^{4}\cdot x^{4}}$).

Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются.

Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши.

Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат. Оптимальное возведение в степень соответствует построению кратчайшей аддитивной цепочки.